1. Field of the Invention
The present invention relates to the management of page table pages by the virtual memory management system of a multitasking computer system. More specifically, the present invention relates to removing page table pages from the working set of a process and swapping such page table pages out of primary memory when certain conditions exist.
2. Summary of the Prior Art
Referring to FIG. 1, a computer system 10 is illustrated. The computer system is comprised of a central processing unit (hereinafter "CPU") 20, a plurality of processes 22-30 and primary memory 32, secondary memory 34 and a memory manager 36. Directly connected to the CPU 20 is the primary memory 32. The primary memory 32 is a high speed random access memory. It facilitates CPU processing by permitting fast memory access times. Secondary memory, on the other hand, is usually a large, relatively slow memory device. For example, optical and magnetic disc drives are frequently used as secondary memory. Secondary memory is generally characterized by a slow access time and being relatively inexpensive, compared to primary memory.
In the computer system 10, secondary memory 34 is much larger than primary memory 32. Each process 22-30 performs operations using primary memory 32 which is the only memory that a process "sees." Additional memory is located in the secondary memory and when that information is needed it is transferred into primary memory for the requesting process to access. Since primary memory is small, relative to secondary memory, information is constantly swapped in and out of primary memory. The device which controls the transfer of data between primary and secondary memory is called a virtual memory manager 36 (hereinafter sometimes called "memory manager"). The memory manager 36 utilizes a virtual memory scheme.
Many virtual memory schemes are used in the prior art. An example of one is now illustrated. In FIG. 1, a computer system 10 concurrently runs several processes 22-30 using the CPU 20. Each of these processes 22-30 is allocated a certain portion of primary memory 32. More specifically, each process has a virtual memory space which may far exceed the amount of primary memory that is assigned to it. The portion of each virtual memory space which is currently stored in primary memory is denoted in a "working set" list 22a-30a which is maintained for each process. Thus each process has a "working set," and all other data for the process is stored in secondary memory 34.
The virtual memory manager 36 controls which portions of each process's virtual memory space is to be stored in primary memory and dynamically changes the allocation of primary memory as required.
Referring to FIG. 2, in a virtual memory system, both physical and virtual memory spaces are divided into equally sized "pages."0 The memory manager 36 keeps track of the pages for each process running in the computer 10 by using a table called a "page table" 38. The page table 38 for any one process 22 contains many "page table entries" in (PTEs) 42, each of which denotes the location and status of one page in the process's virtual memory space.
Since a process typically uses many pages of memory there will be a corresponding number of PTEs 42. These PTEs are stored in an array (i.e., table) which itself occupies multiple pages of memory. For example, a process might use four thousand pages of memory and the four thousand PTEs might occupy four pages. Each page used to store PTEs is called a "page table page" 40 (hereinafter "PTP").
When a process has a very large virtual memory space, it may have several PTPs which are rarely or never used. Therefore, it is inefficient to keep these PTPs in primary memory 32. In addition, due to constraints on the size of the working set for a process, it is desirable to remove certain PTPs from a process's working set even before it is appropriate to swap the PTP out to secondary memory 34.